﻿#define _CRT_SECURE_NO_WARNINGS  1
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        vector<int> v;
        unordered_map<string, int> m1;
        unordered_map<string, int> m2;
        int len = words[0].length();
        for (int i = 0; i < words.size(); i++)
        {
            m2[words[i]]++;
        }
        for (int k = 0; k < len; k++)
        {
            vector<string> vs;
            int count = 0;
            for (int i = k; i < s.length(); i += len)
            {
                string vsm(s, i, len);
                vs.push_back(vsm);
            }

            int left = 0;
            int right = 0;
            m1.clear();
            while (right < vs.size())
            {
                while (right < words.size() && right < vs.size())
                {
                    if (m1[vs[right]] < m2[vs[right]])
                        count++;
                    m1[vs[right]]++;
                    right++;
                    if (count == words.size())
                        v.push_back(left * len + k);
                }
                if (m1[vs[left]] <= m2[vs[left]])
                    count--;
                m1[vs[left]]--;
                left++;
                if (right < vs.size())
                    m1[vs[right]]++;
                else
                    break;
                if (m1[vs[right]] <= m2[vs[right]])
                    count++;
                right++;
                if (count == words.size())
                    v.push_back(left * len + k);
            }
        }
        return v;
    }
};

//class Solution
//{
//public:
//    vector<int> findSubstring(string s, vector<string>& words)
//    {
//        vector<int> ret;
//        unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
//        for (auto& s : words) hash1[s]++;
//        int len = words[0].size(), m = words.size();
//        for (int i = 0; i < len; i++) // 执⾏ len 次
//        {
//            unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
//            for (int left = i, right = i, count = 0; right + len <= s.size();
//                right += len)
//            {
//                // 进窗⼝ + 维护 count
//                string in = s.substr(right, len);
//                hash2[in]++;
//                if (hash1.count(in) && hash2[in] <= hash1[in]) count++;
//                // 判断
//                if (right - left + 1 > len * m)
//                {
//                    // 出窗⼝ + 维护 count
//                    string out = s.substr(left, len);
//                    if (hash1.count(out) && hash2[out] <= hash1[out]) count--;
//                    hash2[out]--;
//                    left += len;
//                }
//                // 更新结果
//                if (count == m) ret.push_back(left);
//            }
//        }
//        return ret;
//    }
//};
int main()
{
    Solution s;
    string s1("aaaaaaaaaaaaaa");
    vector<string> vwords{ "aa","aa"};
    s.findSubstring(s1, vwords);
}